package 整数拆分;

import java.util.Arrays;

/**
 * @author: AirMan
 * @date: 2025/5/6 14:55
 * @description:
 */
public class Solution {
    public int integerBreak(int n) {
        // dynamic programming
        // ① dp[i]数组以及含义： dp[i]表示正整数 i 拆分后的乘积最大值
        // ② 状态转移方程：dp[i] = Math.max(dp[i-j] * dp[j], dp[i]) (拆分为2个及2个以上)
        //               dp[i] = Math.max((i-j)*j, dp[i]) (拆分为2个)
        // ③ 初始化dp数组：dp[1] = 1
        // ④ 遍历顺序：从左到由遍历
        // ⑤ 举例推导dp数组：n = 10 ==>
        //                 0    1   2   3   4   5   6   7   8   9   10
        //                      1   1   2   4   6   9   12  18  24  36

        int[] dp = new int[n + 1];
        dp[1] = 1;
//        System.out.println(Arrays.toString(dp));
        for (int i = 2; i <= n; i++) {
//            System.out.println("-------------" + i + "------------");
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = Math.max((i - j) * j, dp[i]);      // 拆分为2个
                dp[i] = Math.max(dp[i - j] * j, dp[i]);   // 拆分为2个及2个以上
//                System.out.println(Arrays.toString(dp));
            }
//            System.out.println("-------------" + i + "------------");
        }
        return dp[n];
    }
}
